home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / qquant.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  8KB  |  406 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    qquant -
  19.  *        quick quant.  The median cut algorithm follows.  This is 
  20.  *    based on heckbert's median cut algoirthm.
  21.  *
  22.  *                Paul Haeberli - 1991
  23.  */
  24. #include "stdio.h"
  25. #include "quant.h"
  26.  
  27. #define DEBUG
  28.  
  29. #define OFFSET_R    3
  30. #define OFFSET_G     2
  31. #define OFFSET_B    1
  32. #define OFFSET_L    0
  33.  
  34. #define MAXCOLORS     (256)
  35. #define NINCHUNK    (100)
  36. #define RDIR        (1)
  37. #define GDIR        (2)
  38. #define BDIR        (3)
  39.  
  40. typedef struct apixel {
  41.     struct apixel *next;
  42.     unsigned char *pix;
  43. } apixel;
  44.  
  45. typedef struct colorvol {
  46.     struct colorvol     *next;
  47.     long        rmin, rmax, rcut, rdev;
  48.     long        gmin, gmax, gcut, gdev;
  49.     long        bmin, bmax, bcut, bdev;
  50.     int         avgdev;
  51.     int            npixels;
  52.     int            splitdir;
  53.     int            number;
  54.     apixel         *pix;
  55. } colorvol;
  56.  
  57. static long ctab[MAXCOLORS][3];
  58. static short rbuf[MAXCOLORS];
  59. static short gbuf[MAXCOLORS];
  60. static short bbuf[MAXCOLORS];
  61. static colorvol *cvarray[MAXCOLORS];
  62. static colorvol *fvols = 0;
  63. static apixel *fpixs = 0;
  64. static colorvol *root = 0;
  65. static int nnodes;
  66.  
  67. static freevol( cv )
  68. colorvol *cv;
  69. {
  70.    if( cv ) {
  71.        cv->next = fvols;
  72.        fvols = cv;
  73.    }
  74. }
  75.  
  76. static colorvol *newvol()
  77. {
  78.     colorvol *cv;
  79.     int i;
  80.  
  81.     if(!fvols) {
  82.        cv = (colorvol *)mymalloc(NINCHUNK*sizeof(colorvol));
  83.        for(i=0; i<NINCHUNK; i++)
  84.        freevol(cv++);
  85.     }
  86.     cv = fvols;
  87.     fvols = fvols->next;
  88.     return cv;
  89. }
  90.  
  91. static freepix( p )
  92. apixel *p;
  93. {
  94.    if( p ) {
  95.        p->next = fpixs;
  96.        fpixs = p;
  97.    }
  98. }
  99.  
  100. static apixel *newpix()
  101. {
  102.     apixel *p;
  103.     int i;
  104.  
  105.     if(!fpixs) {
  106.        p = (apixel *)mymalloc(NINCHUNK*sizeof(apixel));
  107.        for(i=0; i<NINCHUNK; i++)
  108.        freepix(p++);
  109.     }
  110.     p = fpixs;
  111.     fpixs = fpixs->next;
  112.     return p;
  113. }
  114.  
  115. static zaphist(hist,min,max)
  116. long hist[];
  117. long min, max;
  118. {
  119.     int i;
  120.  
  121.     for(i=min; i<=max; i++)
  122.     hist[i] = 0;
  123. }
  124.  
  125. static rangehist(hist,min,max,npix,ravg,rdev)
  126. long hist[];
  127. long min, max, npix, *ravg, *rdev; 
  128. {
  129.     int i;
  130.     long delta, avg, dev;
  131.  
  132.     avg = 0;
  133.     for(i=min; i<=max; i++)  {
  134.     avg += i*hist[i];
  135.     }
  136.     avg = avg/npix;
  137.  
  138.     dev = 0;
  139.     for(i=min; i<=max; i++) {
  140.     delta = i-avg;
  141.     dev += hist[i]*delta*delta;
  142.     }
  143.     *ravg = avg;  
  144.     *rdev = dev>>8;
  145.  
  146.     if(avg == min)
  147.     return 0;
  148.     else
  149.     return 1;
  150. }
  151.  
  152. #define FLAGMAX        (12000)
  153.  
  154. static makenode(rmin,rmax,gmin,gmax,bmin,bmax,pix)
  155. int rmin, rmax, gmin, gmax, bmin, bmax;
  156. apixel *pix; 
  157. {
  158.     colorvol *cv;
  159.     int Rmin, Rmax, Gmin, Gmax, Bmin, Bmax;
  160.     int r, g, b;
  161.     int rok, gok, bok;
  162.     long npixels;
  163.     long rhist[256];
  164.     long ghist[256];
  165.     long bhist[256];
  166.  
  167.     cv = newvol();
  168.     cv->pix = pix;
  169.  
  170.     Rmin = Gmin = Bmin = FLAGMAX;
  171.     Rmax = Gmax = Bmax = -FLAGMAX;
  172.  
  173.     zaphist(rhist,rmin,rmax);
  174.     zaphist(ghist,gmin,gmax);
  175.     zaphist(bhist,bmin,bmax);
  176.  
  177.     npixels = 0;
  178.     while(pix) {
  179.     r = pix->pix[OFFSET_R];
  180.     g = pix->pix[OFFSET_G];
  181.     b = pix->pix[OFFSET_B];
  182.     if(r<Rmin)
  183.         Rmin = r;
  184.     if(g<Gmin)
  185.         Gmin = g;
  186.     if(b<Bmin)
  187.         Bmin = b;
  188.     if(r>Rmax)
  189.         Rmax = r;
  190.     if(g>Gmax)
  191.         Gmax = g;
  192.     if(b>Bmax)
  193.         Bmax = b;
  194.     npixels++;
  195.     rhist[r]++;
  196.     ghist[g]++;
  197.     bhist[b]++;
  198.     pix = pix->next;
  199.     }
  200.     if(npixels == 0)
  201.     return;
  202.  
  203.     cv->npixels = npixels;
  204.     cv->rmin = Rmin;
  205.     cv->gmin = Gmin;
  206.     cv->bmin = Bmin;
  207.     cv->rmax = Rmax;
  208.     cv->gmax = Gmax;
  209.     cv->bmax = Bmax;
  210.     rok = rangehist(rhist,cv->rmin,cv->rmax,npixels,&cv->rcut,&cv->rdev);
  211.     gok = rangehist(ghist,cv->gmin,cv->gmax,npixels,&cv->gcut,&cv->gdev);
  212.     bok = rangehist(bhist,cv->bmin,cv->bmax,npixels,&cv->bcut,&cv->bdev);
  213.  
  214.     if(rok && cv->rdev>=cv->gdev && cv->rdev>=cv->bdev) 
  215.     cv->splitdir = RDIR;
  216.     else if(gok && cv->gdev>=cv->rdev && cv->gdev>=cv->bdev) 
  217.     cv->splitdir = GDIR;
  218.     else  if(bok)
  219.     cv->splitdir = BDIR;
  220.     else
  221.     cv->splitdir = 0;
  222.  
  223.     cv->avgdev = cv->rdev+cv->gdev+cv->bdev;
  224. #ifdef OLDWAY
  225.     cv->avgdev = ILUM(cv->rdev,cv->gdev,cv->bdev);
  226. #endif
  227.     cv->next = root;
  228.     root = cv;
  229.     nnodes++;
  230. }
  231.  
  232. splitlist(pix,pix0,pix1,level,dir)
  233. apixel *pix;
  234. apixel **pix0, **pix1;
  235. int level, dir;
  236. {
  237.     apixel *p0, *p1, *np;
  238.  
  239.     p0 = 0;
  240.     p1 = 0;
  241.     switch(dir) {
  242.     case RDIR:
  243.         while(pix) {
  244.         np = pix->next;
  245.         if((int)(pix->pix[OFFSET_R])<level) {
  246.             pix->next = p0;
  247.             p0 = pix;
  248.         } else {
  249.             pix->next = p1;
  250.             p1 = pix;
  251.         }
  252.         pix = np;
  253.         }
  254.         break;
  255.     case GDIR:
  256.         while(pix) {
  257.         np = pix->next;
  258.         if((int)(pix->pix[OFFSET_G])<level) {
  259.             pix->next = p0;
  260.             p0 = pix;
  261.         } else {
  262.             pix->next = p1;
  263.             p1 = pix;
  264.         }
  265.         pix = np;
  266.         }
  267.         break;
  268.     case BDIR:
  269.         while(pix) {
  270.         np = pix->next;
  271.         if((int)(pix->pix[OFFSET_B])<level) {
  272.             pix->next = p0;
  273.             p0 = pix;
  274.         } else {
  275.             pix->next = p1;
  276.             p1 = pix;
  277.         }
  278.         pix = np;
  279.         }
  280.         break;
  281.     }
  282.     *pix0 = p0;
  283.     *pix1 = p1;
  284. }
  285.  
  286. static divspace(cv)
  287. colorvol *cv;
  288. {
  289.     apixel *pix0, *pix1;
  290.  
  291.     switch(cv->splitdir) {
  292.     case RDIR:
  293.         splitlist(cv->pix,&pix0,&pix1,cv->rcut,RDIR);
  294.         makenode(cv->rmin,cv->rcut-1,cv->gmin,cv->gmax,cv->bmin,cv->bmax,pix0); 
  295.         makenode(cv->rcut,cv->rmax,  cv->gmin,cv->gmax,cv->bmin,cv->bmax,pix1); 
  296.         break;
  297.     case GDIR:
  298.         splitlist(cv->pix,&pix0,&pix1,cv->gcut,GDIR);
  299.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gcut-1,cv->bmin,cv->bmax,pix0); 
  300.         makenode(cv->rmin,cv->rmax,cv->gcut,cv->gmax,  cv->bmin,cv->bmax,pix1); 
  301.         break;
  302.     case BDIR:
  303.         splitlist(cv->pix,&pix0,&pix1,cv->bcut,BDIR);
  304.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gmax,cv->bmin,cv->bcut-1,pix0); 
  305.         makenode(cv->rmin,cv->rmax,cv->gmin,cv->gmax,cv->bcut,cv->bmax  ,pix1); 
  306.         break;
  307.     default:
  308.         fprintf(stderr,"baaaaaad poop %d\n",cv->splitdir);
  309.         exit(1);
  310.     }
  311.     nnodes--;
  312.     cv->pix = 0;
  313.     cv->npixels = 0;
  314.     cv->avgdev = 0;
  315. }
  316.  
  317. cmap *qquant( unsigned long *lbuf, unsigned short *sbuf, int npixels, int baseci, int ncolors, int mode )
  318. {
  319.     int i, r, g, b;
  320.     int ci, bigest;
  321.     colorvol *bigcv, *cv, *ncv;
  322.     apixel *pix, *pixlist, *npix;
  323.     int n;
  324.  
  325. /* check ncolors */
  326.     if(ncolors<1) {
  327.     fprintf(stderr,"quant: num colors is less than 1\n");
  328.     exit(1);
  329.     }
  330.     if(ncolors>MAXCOLORS) {
  331.     fprintf(stderr,"quant: num colors exceeds %d\n",MAXCOLORS);
  332.     exit(1);
  333.     }
  334.  
  335. /* make a list out of all the pixels */
  336.     pixlist = 0;
  337.     n = npixels;
  338.     for(n=0; n<npixels; n++) {
  339.     pix = newpix(); 
  340.     pix->next = pixlist;
  341.     pixlist = pix;
  342.     pix->pix = (unsigned char *)(lbuf+n);
  343.     }
  344.  
  345. /* create the root node */
  346.     root = NULL;
  347.     makenode(0,255,0,255,0,255,pixlist); 
  348.  
  349. /* repeat division of the best piece for ncolors */
  350.     nnodes = 1;
  351.     while(nnodes<ncolors) {
  352.     bigcv = 0;
  353.     bigest = 0;
  354.     cv = root;
  355.     if(mode) {    /* use number of pixels */
  356.         while(cv) {
  357.         if(cv->splitdir && cv->npixels>bigest) {
  358.              bigcv = cv;
  359.              bigest = cv->npixels;
  360.         }
  361.         cv = cv->next;
  362.         }
  363.     } else {    /* use avg deviation */
  364.         while(cv) {
  365.         if(cv->splitdir && cv->avgdev>bigest) {
  366.              bigcv = cv;
  367.              bigest = cv->avgdev;
  368.         }
  369.         cv = cv->next;
  370.         }
  371.     }
  372.     if(bigcv)
  373.         divspace(bigcv);
  374.     else {
  375. #ifdef NOTDEf
  376.         fprintf(stderr,"Ncolor reduced to %d from %d\n",nnodes,ncolors);
  377. #endif
  378.         ncolors = nnodes;
  379.         break;
  380.     }
  381.     }
  382.  
  383. /* set the color indexes */
  384.     cv = root;
  385.     ci = 0;
  386.     while(cv) {
  387.     pix = cv->pix;
  388.     if(pix) {
  389.         while(pix) {
  390.         sbuf[(pix->pix-((unsigned char *)lbuf))/sizeof(long)] = baseci+ci;
  391.         npix = pix->next;
  392.         freepix(pix);
  393.         pix = npix;
  394.         }
  395.         rbuf[ci] = cv->rcut;
  396.         gbuf[ci] = cv->gcut;
  397.         bbuf[ci] = cv->bcut;
  398.         ci++;
  399.     }
  400.     ncv = cv->next;
  401.     freevol(cv);
  402.     cv = ncv;
  403.     }
  404.     return newcmap(rbuf,gbuf,bbuf,0,ci);
  405. }
  406.